#include <hash.h>

static int tree_add(NODE *new, NODE **root);
static int tree_depth(NODE *root);
static NODE *tree_max(NODE *root);
static NODE *tree_min(NODE *root);
static void turn_left(NODE **root);
static void turn_right(NODE **root);
static void tree_balance(NODE **root);
static char *tree_find(const char *en, NODE *root);
static int hash_index(const char *en, HASH *hash);

static int tree_add(NODE *new, NODE **root)
{
    NODE *tail = *root;

    new->left = NULL;
    new->right = NULL;

    if (*root == NULL)
        *root = new;
    else
    {
        while (1)
        {
            if (strcmp(new->en, tail->en) >= 0)
            {
                if (tail->right == NULL)
                {
                    tail->right = new;
                    break;
                }
                tail = tail->right;
            }
            else
            {
                if (tail->left == NULL)
                {
                    tail->left = new;
                    break;
                }
                tail = tail->left;
            }
        }
    }

    return 0;
}

NODE *tree_max(NODE *root)
{
    while (root->right != NULL)
        root = root->right;
    return root;
}

NODE *tree_min(NODE *root)
{
    while (root->left != NULL)
        root = root->left;
    return root;
}

static void turn_left(NODE **root)
{
    NODE *tail = (*root)->right;

    tree_min(tail)->left = *root;
    (*root)->right = NULL;
    *root = tail;
}

static void turn_right(NODE **root)
{
    NODE *tail = (*root)->left;

    tree_max(tail)->right = *root;
    (*root)->left = NULL;
    *root = tail;
}

static int tree_depth(NODE *root)
{
    if (root == NULL)
        return 0;
    return 1 + (tree_depth(root->left) > tree_depth(root->right) ? tree_depth(root->left): tree_depth(root->right));
}

void _tree_balance(NODE **root)
{
    int l, r;

    if (*root == NULL)
        return;

    l = tree_depth((*root)->left);
    r = tree_depth((*root)->right);

    /* printf("l = %d, r = %d\n", l, r); */

    while (l - r > 1 || l - r < -1)
    {
        if (l > r)
            turn_right(root);
        else
            turn_left(root);
        l = tree_depth((*root)->left);
        r = tree_depth((*root)->right);
    }

    _tree_balance(&(*root)->left);
    _tree_balance(&(*root)->right);
}

static void tree_balance(NODE **root)
{
    int l, r;

    if (*root == NULL)
        return;

    do
    {
        /* printf("fro root = %p, *root = %p\n", root, *root); */
        _tree_balance(root);
        /* printf("end root = %p\n", root); */
        l = tree_depth((*root)->left);
        r = tree_depth((*root)->right);
    } while (l - r > 1 || l - r < -1);

    /* printf("balance root = %p!\n", root); */
}

static char *tree_find(const char *en, NODE *root)
{
    int ret;

    while (root)
    {
        ret = strcmp(en, root->en);
        if (ret > 0)
            root = root->right;
        else if (ret < 0)
            root = root->left;
        else
            return root->cn;
    }

    return NULL;
}


static int hash_index(const char *en, HASH *hash)
{
    int ret = 0;

    while (*en)
    {
        ret += *en++;
    }
    return ret % hash->max;
}

char *hash_find(char *en, HASH *hash)
{
    return tree_find(en, hash->list[hash_index(en, hash)]);
}

HASH *hash_create(NODE *head, int node_num)
{
    HASH *hash = NULL;
    NODE *tail = NULL;
    int i, index;

    hash = (HASH *)malloc(sizeof(HASH));
    ERRP(NULL == hash, goto ERR1, 2, "malloc hash failed!\n");

    hash->max = node_num * 2;
    hash->list = (NODE **)malloc(hash->max * sizeof(NODE *));
    ERRP(NULL == hash->list, goto ERR2, 2, "malloc hash list failed!\n");

    memset(hash->list, 0, sizeof(NODE *) * hash->max);

    for (tail = head->next; tail != head; tail = tail->next)
    {
        index = hash_index(tail->en, hash);
        tree_add(tail, hash->list + index);
    }

    for (i = 0; i < hash->max; i++)
    {
        tree_balance(hash->list + i);
        /* printf("max = %d, i = %d\n", hash->max, i); */
    }

    return hash;
ERR2:
    free(hash);
ERR1:
    return NULL;
}

void hash_destroy(HASH *hash)
{
    free(hash->list);
    free(hash);
}

